//给定 N 个人的出生年份和死亡年份，第 i 个人的出生年份为 birth[i]，死亡年份为 death[i]，实现一个方法以计算生存人数最多的年份。 
//
// 你可以假设所有人都出生于 1900 年至 2000 年（含 1900 和 2000 ）之间。如果一个人在某一年的任意时期处于生存状态，那么他应该被纳入那一
//年的统计中。例如，生于 1908 年、死于 1909 年的人应当被列入 1908 年和 1909 年的计数。 
//
// 如果有多个年份生存人数相同且均为最大值，输出其中最小的年份。 
//
// 
//
// 示例： 
//
// 
//输入：
//birth = [1900, 1901, 1950]
//death = [1948, 1951, 2000]
//输出： 1901
// 
//
// 
//
// 提示： 
//
// 
// 0 < birth.length == death.length <= 10000 
// birth[i] <= death[i] 
// 
//
// Related Topics 数组 计数 👍 72 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2025-09-07 13:10:43
 * @description 面试题 16.10.生存人数
 */
public class LivingPeopleLcci{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 LivingPeopleLcci fun=new LivingPeopleLcci();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 // 答案一定在birth数组中的其中一个
    public int maxAliveYear(int[] birth, int[] death) {
		int n = birth.length;
		int[] a=new int[2003]; // 差分数组a
		for (int i = 0; i < n; i++)
		{
			int x = birth[i], y = death[i];
			a[x] += 1; a[y+1]-=1; // 表示对区间[x, y]的元素全部加一
		}
		// 最大人数  坐标  当前差分和
		int mx = 0, idx = 0, sum=0;
		for (int i = 1900; i <= 2000; ++i) //计算差分数组的前缀和，每一个前缀和对应问题的每一个位置的人数
		{
			sum += a[i];
			if (mx < sum)
			{
				mx = sum;
				idx = i;
			}
		}
		return idx;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
